package com.huangpeng.algorithm.dataStructure;

/**
 * @Author huangpeng
 * @Title 0-1 背包问题升级版
 * @Package
 * @Date 2021/7/27 10:01
 * @Description 动态规划实现
 * @Version 1.0
 */
public class DynamicProgramming {
    private int maxV = Integer.MIN_VALUE; // 结果放到 maxV 中
    private int[] items = {2,2,4,6,3};  // 物品的重量
    private int[] value = {3,4,8,9,6}; // 物品的价值
    private int n = 5; // 物品个数
    private int w = 9; // 背包承受的最大重量

    /**
     * 背包问题升级使用动态规划求解
     * @param weight
     * @param value
     * @param n
     * @param w
     * @return
     */
    public int knapsack3(int[] weight,int[] value,int n,int w){
        int[][] states = new int[n][w + 1];
        //初始化states
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < w + 1; j++) {
                states[i][j] = -1;
            }
        }
        states[0][0] = 0;// 第一行的数据要特殊处理
        states[0][weight[0]] = value[0];
        for (int i = 1; i < n; i++) {// 动态规划，状态转移
            for (int j = 0; j <= w; j++) {// 不选择第 i 个物品
                if(states[i - 1][j] >= 0){
                    states[i][j] = states[i - 1][j];
                }
            }
            for (int j = 0; j <= w - weight[i]; j++) {// 选择第 i 个物品
                if(states[i - 1][j] >= 0){
                    int v = states[i - 1][j] + value[i];
                    if(v > states[i][j + weight[i]]){
                        states[i][j + weight[i]] = v;
                    }
                }
            }
        }
        //找出最大值
        int maxValue = -1;
        for (int i = 0; i <= w; i++) {
            if(states[n - 1][i] > maxValue){
                maxValue = states[n - 1][i];
            }
        }

        return maxValue;
    }

    /**
     * 动态规划-双十一满减活动
     * @param items 商品价格
     * @param n 商品个数
     * @param w 表示满减条件，比如 200
     */
    public static void double11advance(int[] items, int n, int w){
        boolean[][] states = new boolean[n][3 * w];//超过3倍就没有薅羊毛的价值了
        states[0][0] = true;// 第一行的数据要特殊处理
        states[0][items[0]] = true;
        for (int i = 1; i < n; i++) {// 动态规划
            for (int j = 0; j < 3 * w; j++) {// 不购买第 i 个商品
                if(states[i - 1][j] == true){
                    states[i][j] = states[i - 1][j];
                }
            }
            for (int j = 0; j < 3 * w - items[i]; j++) {// 购买第 i 个商品
                if(states[i - 1][j] == true){
                    states[i][j + items[i]] = true;
                }
            }
        }
        int j;
        for (j = w; j < 3 * w + 1; j++) {
            if(states[n - 1][j] == true){// 输出结果大于等于 w 的最小值
                break;
            }
        }
        if(j == 3 * w + 1){
            return;// 没有可行解
        }
        for (int i = n -1; i >= 1; i--) {// i 表示二维数组中的行，j 表示列
            if(j - items[i] >= 0 && states[i - 1][j - items[i]] == true){
                System.out.print(items[i] + " "); // 购买这个商品
                j = j -items[i];
            }// else 没有购买这个商品，j 不变。
        }
        if (j != 0){
            System.out.print(items[0]);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        DynamicProgramming d = new DynamicProgramming();
        int maxValue = d.knapsack3(d.items,d.value,d.n,d.w);
        System.out.println("********** " + maxValue);

        int[] items = {30,12,5,8,33,21,33,54,22,2};
        int n = 10;
        int w = 100;
        DynamicProgramming.double11advance(items,n,w);
    }
}
